{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 17.4 Dynamic tables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.4-1\n",
    "\n",
    "> Suppose that we wish to implement a dynamic, open-address hash table. Why might we consider the table to be full when its load factor reaches some value $\\alpha$ that is strictly less than 1? Describe briefly how to make insertion into a dynamic, open-address hash table run in such a way that the expected value of the amortized cost per insertion is $O(1)$. Why is the expected value of the actual cost per insertion not necessarily $O(1)$ for all insertions?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.4-2\n",
    "\n",
    "> Show that if $\\alpha_{i-1} \\ge 1/2$ and the $i$th operation on a dynamic table is TABLE-DELETE, then the amortized cost of the operation with respect to the potential function (17.6) is bounded above by a constant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\displaystyle \\hat{c_i} \n",
    "&=& \\displaystyle c_i + \\Phi_i - \\Phi_{i-1} \\\\\n",
    "&=& \\displaystyle 1 + (2 \\cdot num_i - size_i) - (2 \\cdot (num_i + 1) - size_i) \\\\\n",
    "&=& -1\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 17.4-3\n",
    "\n",
    "> Suppose that instead of contracting a table by halving its size when its load factor drops below $1/4$, we contract it by multiplying its size by $2/3$ when its load factor drops below $1/3$. Using the potential function\n",
    "\n",
    "> $\\Phi(T) = | 2 \\cdot T.num - T.size |$,\n",
    "\n",
    "> show that the amortized cost of a TABLE-DELETE that uses this strategy is bounded above by a constant."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If $1/3 < \\alpha_i \\le 1/2$,\n",
    "\n",
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\hat{c_i} &=& c_i + \\Phi_i - \\Phi_{i-1} \\\\\n",
    "&=& 1 + (size_i - 2 \\cdot num_i) - (size_i - 2 \\cdot (num_i + 1)) \\\\\n",
    "&=& 3\n",
    "\\end{array}\n",
    "$$\n",
    "\n",
    "If the $i$th operation does trigger a contraction,\n",
    "\n",
    "$$\n",
    "\\frac{1}{3} size_{i-1} = num_i + 1 \\\\\n",
    "size_{i-1} = 3 (num_i + 1) \\\\\n",
    "size_{i} = \\frac{2}{3} size_{i-1} = 2 (num_i + 1)\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\begin{array}{rll}\n",
    "\\hat{c_i} &=& c_i + \\Phi_i - \\Phi_{i-1} \\\\\n",
    "&=& (num_i + 1) + [2 \\cdot (num_i + 1) - 2 \\cdot num_i] - [3 \\cdot (num_i + 1) - 2 \\cdot (num_i + 1)] \\\\\n",
    "&=& 2\n",
    "\\end{array}\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
